package ext;

import java.util.*;
import org.junit.*;

import util.ArrayGenerator;
public class Baidu7 {

    //给二叉树节点增加一个兄弟节点
    class Node {
        Node left, right, bro;
        int val;
    }

    //层序遍历，查看父节点的子节点时判断左右是否同时不空
    public Node addBro(Node root) {
        Node cur = root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(cur);

        while (!queue.isEmpty()) {
            cur = queue.poll();
            if (cur.left != null && cur.right != null) {
                cur.left.bro = cur.right;
                cur.right.bro = cur.left;
            }
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);
        }
        return root;
    }


    public void quickSort(int[] nums, int left, int right) {
        //快排非递归实现
        /* 
            非递归实现与递归大致差不多，只不过需要用栈保存left和right
            注意参数中使用left和right要与入栈顺序相反。
        */
        Stack<Integer> stack = new Stack<>();
        stack.push(left);
        stack.push(right);

        while (!stack.isEmpty()) {

            /* 一趟快速排序的逻辑，只是left 和right中取得 */
            right = stack.pop();
            left = stack.pop();

            int hi = right, lo = left, pivot = nums[lo];

            while (lo < hi) {
                while (lo < hi && nums[hi] >= pivot) hi--;
                while (lo < hi && nums[lo] <= pivot) lo++;
                swap(nums, lo, hi);
            }
            swap(nums, lo, left);

            //正常情况下需要返回lo，然后按照(left, lo - 1)(lo, right)切分来两段
            if (left < lo - 1) {
                stack.push(left);
                stack.push(lo - 1);
            }
            if (lo + 1 < right) {
                stack.push(lo + 1);
                stack.push(right);
            }
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    @Test
    public void test1() {
        int[] nums = new int[]{5,2,3,1,4};
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    @Test
    public void test() {
        for (int i = 0; i < 10000; i++) {
            int[] nums = ArrayGenerator.getArray(100, 20);
            quickSort(nums, 0, 19);
            String s1 = Arrays.toString(nums);
            Arrays.sort(nums);
            String s2 = Arrays.toString(nums);
            if (!s1.equals(s2)) System.out.println(s1);
        }         
        System.out.println("finnished");
    }
    
}
